One of the things used commonly in every day life, and in particular in computerized systems is communication. The need for communication is obvious. People throughout the world need to share information among them, talk through the phone, see movies through the internet, send SMS (short message service) messages etc. There is a growing demand for communication. All over the world more and more people are using cellular phones. More and more people are using cable modems and ADSL, people nowadays download video movies to their cellular phones, and also perform video conferences via cellular phones.
An important resource in communications is the bandwidth. If bandwidth was unlimited, issues like QoS (quality of service) were not relevant. However, since this is not the case, bandwidth is and will be an important issue. Common applications such as audio streaming and video streaming consume today major portions of the bandwidth. More and more people download movies in DivX format (MPEG-4).
Bandwidth is an important resource in computer networks. The bandwidth can be considered as an important factor in networks performance. There are a few common ways to improve the performance of a network: bandwidth management which allows better utilization of existing network capacity by aligning network with organizations priorities; caching which increases the overall capacity of the network. In particular, caching of web traffic helps to reduce response time for access to web content; Finally, by using data compression, we can identify different protocol segments in a packet and reduce header information any payload information significantly.
We consider data compression in packet networks, in which data is transmitted by partitioning it into packets. Packet compression allows better bandwidth utilization of a communication line resulting in much smaller amounts of packet drops, more simultaneous sessions, and a smooth and fast behavior of applications (see, e.g., [34]).
Packet compression can be obtained by a combination of header compression [16] and payload compression, which may be complementary methods. Many dictionary compression algorithms were developed following the seminal papers of Lempel and Ziv (see, [33, 36, 37]).
In dictionary compression, an input sequence encoding is based on a dictionary that is constructed dynamically according to the given text. The compression is done in a streaming fashion, enabling to leverage on redundancy in the input sequence.
In many packet networks, including ATM [2], Frame Relay [5], Wireless, and others, packets are sent via different routes, and may arrive reordered, due to different network characteristics, or due to retransmissions in case of dropped packets. Since streaming compression assumes that the compressed sequence arrives at the decoder in the order in which it was sent by the encoder, the decoder must hold packets in a buffer until all preceding packets arrive. This causes decoding latency, which may be unacceptable in some applications.
To alleviate decoding latency, standard stateless packet compression algorithms are based on a packet-by-packet compression. For each packet, its payload is compressed using a dictionary compression algorithm, independently to other packets. While the decoding latency is addressed properly, this may often result in poor compression quality, since the inherent redundancy within a packet is significantly smaller than in the entire stream.
There is an ongoing need for methods, apparatus and computer-readable code provide improved compression quality and/or reduced or eliminated coding latency.
The following documents are believed to be the represent the state of the art:
1) U.S. Pat. No. 6,388,584 of Dorward and Quinlan;
2) S. Dorward and S. Quinlan. Robust data compression of network packets.
Bell Labs, Lucent Technologies, July 2000. Unpublished manuscript.